package com.lft.sort01.bubble_sort;

import java.util.Arrays;

public class BubbleSort {
	public static void main(String[] args) {
		int[] arr = {3, 9, -1, 10, 20};
		// int[] arr = {1, 2, 3, 4, 7, 6, 5};
		System.out.println(Arrays.toString(bubbleSort(arr)));
	}
	
	public static int[] bubbleSort(int[] arr) {
		// 冒泡排序的时间复杂度：平均：O(n^2)，最差：O(n^2)
		int temp;
		// 表示是否进行过交换。
		boolean flag = false;
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = 0; j < arr.length - 1 - i; j++) {
				// 如果前面的数比后面的数大，则交换。
				if (arr[j] > arr[j + 1]) {
					// 如果交换过顺序，就将 flag 设置 为 true
					flag = true;
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
			System.out.println("第 " + (i + 1) + " 排序完成：" + Arrays.toString(arr));
			// 如果在一趟排序中，一次交换都没发生过。
			if (!flag) {
				break;
			} else {
				// 重置 flag ，进行下次判断。
				flag = false;
			}
		}
		return arr;
		
		// 为了便于理解，以下会展示冒泡排序的演变过程。
		// 第一趟排序，就是将最大的数排到最右端。
		// int temp;
		// for (int i = 0; i < arr.length - 1; i++) {
		// 	// 如果前面的数比后面的数大，则交换。
		// 	if (arr[i] > arr[i + 1]) {
		// 		temp = arr[i];
		// 		arr[i] = arr[i + 1];
		// 		arr[i + 1] = temp;
		// 	}
		// }
		// System.out.println("第一趟排序完成：" + Arrays.toString(arr));
		//
		// // 第二趟排序，就是将第二大的数排到最右端第二位。
		// for (int i = 0; i < arr.length - 1 - 1; i++) {
		// 	// 如果前面的数比后面的数大，则交换。
		// 	if (arr[i] > arr[i + 1]) {
		// 		temp = arr[i];
		// 		arr[i] = arr[i + 1];
		// 		arr[i + 1] = temp;
		// 	}
		// }
		// System.out.println("第二趟排序完成：" + Arrays.toString(arr));
		//
		// // 第三趟排序，就是将第三大的数排到最右端第三位。
		// for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
		// 	// 如果前面的数比后面的数大，则交换。
		// 	if (arr[i] > arr[i + 1]) {
		// 		temp = arr[i];
		// 		arr[i] = arr[i + 1];
		// 		arr[i + 1] = temp;
		// 	}
		// }
		// System.out.println("第三趟排序完成：" + Arrays.toString(arr));
		//
		// // 第四趟排序，就是将第四大的数排到最右端第四位。
		// for (int i = 0; i < arr.length - 1 - 1 - 1 - 1; i++) {
		// 	// 如果前面的数比后面的数大，则交换。
		// 	if (arr[i] > arr[i + 1]) {
		// 		temp = arr[i];
		// 		arr[i] = arr[i + 1];
		// 		arr[i + 1] = temp;
		// 	}
		// }
		// System.out.println("第四趟排序完成：" + Arrays.toString(arr));
		//
	}
}
